package cn.edu.jxau.test;

import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ExecutionException;

public class Main {

	public static void main(String[] args) throws InterruptedException, ExecutionException {

		Node<Integer> root = new Node<>(10);
		root.left = new Node<>(5);
		root.right = new Node<>(12);
		root.left.left = new Node<>(4);
		root.left.right = new Node<>(7);
		path(root, 22);
	}

	public static void path(Node<Integer> root, int sum) {

		path(root, new LinkedList<Integer>(), sum);
	}

	private static void path(Node<Integer> node, List<Integer> path, int sum) {

		if (node == null || sum < 0) {
			return;
		}
		path.add(node.data);
		if (node.left == null && node.right == null) {
			if (node.data == sum) {
				for (int i = 0, end = path.size(); i < end; i++) {
					System.out.print(path.get(i) + "\t");
				}
			}
		}
		path(node.left, path, sum - node.data);
		path(node.right, path, sum - node.data);
		path.remove(path.size() - 1);
	}
}

class Node<T> {

	public T data;
	public Node<T> right;
	public Node<T> left;

	public Node(T data) {
		this.data = data;
	}
}